1. Technical Field
The present invention relates to a method and a device for optimal technology mapping in logic circuit designs; in particular, a method and device for optimally mapping circuit delay and other cost functions on directed acyclic graphs.
2. Discussion of Related Art
In high-performance logic circuit designs, meeting delay targets in the control logic imposes a major challenge. Control logic usually undergoes changes till very late in the design cycle. Control logic is quite often not regular enough to lead to an intuitive data-flow type implementation. Logic synthesis is therefore necessary to meet the project schedules for these high-performance designs, and ensure a correct implementation of the irregular subcircuits. Logic synthesis is the process of automatically generating optimized logic-level representation from a high-level description. With the rapid advances in integrated circuit technology and the resultant growth in design complexity, designers increasingly rely on logic synthesis to shorten the design time while achieving performance objectives.
Known logic synthesis systems typically employ a three-phase methodology. The phases are usually: (1) technology independent optimization; (2) technology mapping; and (3) timing corrections. See, L. Stok et al. Booledozer logic synthesis for asics. IBM Journal of Research and Development, Vol. 40(4): 407-430, July 1996. Varying the three phases impact greatly the structure and cost functions of technology mapped logic. Cost functions affect the area of the cells, delay through the cells or other measures of merit. See "Technology mapping in MIS", E. Detjens, G. Gannot, R. Rudell, A. Sangiovanni-Vincentelli, and A. Wang, November 1987. Minimizing delay in the technology mapping phase had been an important goal in the aforementioned designs.
Traditional technology mapping can be described as a 3-step procedure. First, the technology-independent circuit is decomposed in terms of some primitives to have some well-defined logic structure to aid the technology mapping process. This phase is typically referred to as the circuit decomposition phase. Second, a pattern matcher performs analysis on the circuit and the library, either structurally or functionally, and determines a set of matches for all nodes in the circuit. The third and final step identifies the best set of matches (based on some cost functions) for the circuit such that every node in the circuit is covered exactly once. The final set of matches that cover all the nodes in the circuit are used to describe the circuit in terms of the target technology library cells.
Another target of optimization in circuit synthesis is the reduction of the area of the cells. In K. Keutzer. Dagon: "Technology binding and local optimization by dag matching", In Proc of the 24th Design Automation Conference, June 1987, a technology independent net list description of a combinational circuit is partitioned into a forest of trees, then using a tree pattern matching automation, individual trees are matched to create a technology bound circuit. The least cost in size or area is obtained. Drawback of this technique is that it is only optimal for trees. Most circuits consist of directed acyclic graphs (DAGs) and require a non-trivial decomposition of the DAGs into trees.
Technology mapping works mostly on a fixed subject graph. Therefore, the result is highly dependent on the preceding decomposition of the network. In E. Lehman, Y. Watanabe, J. Grodstein, and H. Harkness, "Logic decomposition during technology mapping", IEEE Trans on CAD, 16(8):813-834, August, 1997, logic decomposition is combined with the mapping phase itself to avoid problems of optimizations in disconnected phases. The proposed algorithm runs on tree leaf DAGs. However, exhaustive embedding of decompositions leads to a large increase in the subject graph, which renders the algorithm impractical for larger sizes of circuits.
A need therefore exists for a simple and practical device and method for logic circuit design that is delay optimized for DAGs.